import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeMap;

import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.Point;
import com.vividsolutions.jts.io.ParseException;
import com.vividsolutions.jts.io.WKTReader;

/* 基于点的kNN查询*/
public class KNNTest {
	public void pointArray(double X,double Y,double range,int k) throws Exception{
		/*计算该点在所给range层级上编码的geohash*/
		double latlength=range*2;
		int l=(int) (2*Math.floor(Logarithm.log(180/latlength, 2)));
		int level=l+1;
		String geohash=prefixGeohash(X, Y, level);
		/*将目标点转换成Geometry*/
		String pointString="POINT"+"("+X+" "+Y+")";
		GeometryFactory geometryFactory=new GeometryFactory();
	    WKTReader reader = new WKTReader( geometryFactory );    
        Point point = (Point) reader.read(pointString); 
        check(X, Y, geohash, point, range, k);	
	}
	/*该方法为计算该点在所给range层级上编码的geohash*/
	private String prefixGeohash(double X,double Y,int level){
		int key=level/5;
		Geohash geohash=new Geohash();
		String prefix=geohash.encode(Y, X).substring(0,key);
		return prefix;		
	}
	/*对得到的点进行排序，取前k个值，若不够扩大范围重新查询*/
	private void check(double X,double Y,String geohash,Point point,double range,int k) throws Exception{
		ArrayList<String> pointArrayList =new ArrayList<String>();
		pointArrayList=query(geohash);
		TreeMap< Double, String> GeoTreeMap=new TreeMap< Double, String>();
		GeoTreeMap=pointKNN(pointArrayList, point, range);
		if(GeoTreeMap.size()>=k){
			int i=0;
			Iterator<Double> iterator=GeoTreeMap.keySet().iterator();
			while(iterator.hasNext()){
				i++;
				if(i<=k){
					System.out.println(GeoTreeMap.get(iterator.next()));
				}
				else
					break;
			}
		}
		else{
			System.out.println("i am here");
			double latlength=range*2;
			int l=(int) (2*Math.floor(Logarithm.log(180/latlength, 2)));
			int level=l+1;
			if(level/5==0){
				Iterator<Double> iterator=GeoTreeMap.keySet().iterator();
				while(iterator.hasNext()){
					System.out.println(GeoTreeMap.get(iterator.next()));
				}
			}
			else
			pointArray(X,Y,range*2,k);
		}
	}
	/*参数为目标点以range层级编码的geohash值，返回一个集合近似于查询范围*/
	private ArrayList<String> query(String geohash) throws Exception{	
		String [] queryStrings=new String[9];
		/*计算该geohash区域周围八个geohash值*/
		queryStrings=GeohashEight.expand(geohash,"");
		queryStrings[8]=geohash;
		ArrayList<String> queryArray=new ArrayList<String>();
		for(int i=0;i<9;i++){
			if(queryStrings[i].length()>0){
				queryArray.add(queryStrings[i]);
			}
		}
		/*依次查询这九个点区域中包含的点*/
		ArrayList<String> pointArrayList =new ArrayList<String>();
		HBaseSQLDriverTest test=new HBaseSQLDriverTest();
		for(int i=0;i<queryArray.size();i++){
			long startTime1 = System.currentTimeMillis();
			pointArrayList=test.query("select rowkey from suijidian where rowkey LIKE '"+queryArray.get(i)+"%'");
			long endTime1 = System.currentTimeMillis();
			System.out.println("数据库第"+i+"次查询时间："+(endTime1-startTime1)+"ms");
		}	
		return pointArrayList;	
	}
	/*该方法为对这九个区域内的点依次与目标点计算距离，取符合条件的点加入TreeMap排序*/
	private TreeMap< Double, String> pointKNN(ArrayList<String> arrayList,Point point,double range) throws ParseException{
		TreeMap<Double, String> GeoTreeMap=new TreeMap< Double, String>();
		for(int i=0;i<arrayList.size();i++){
			String geohash=arrayList.get(i);
			Geohash geo=new Geohash();
			double lonlat[]=geo.decode(geohash);
			String pointString="POINT"+"("+lonlat[1]+" "+lonlat[0]+")";
			GeometryFactory geometryFactory=new GeometryFactory();
		    WKTReader reader = new WKTReader( geometryFactory );    
	        Point goalpoint = (Point) reader.read(pointString);  
	        double distance=goalpoint.distance(point);
	        if(distance<=range)
	        GeoTreeMap.put(distance, arrayList.get(i));
	        
		}
         return GeoTreeMap;		
	}
	/*不用索引的直接查询*/
	public void sQuery(double X,double Y,double range,int k) throws Exception{
		String pointString="POINT"+"("+X+" "+Y+")";
		GeometryFactory geometryFactory=new GeometryFactory();
	    WKTReader reader = new WKTReader( geometryFactory );    
        Point point = (Point) reader.read(pointString); 
        ArrayList<String> pointXArrayList =new ArrayList<String>();
        ArrayList<String> pointYArrayList =new ArrayList<String>();
        HBaseSQLDriverTest test=new HBaseSQLDriverTest();
        pointXArrayList=test.query("select X from suijidian");
        pointYArrayList=test.query("select Y from suijidian");
        TreeMap<Double, String> GeoTreeMap=new TreeMap< Double, String>();
        Geohash geohash=new Geohash();
        for(int i=0;i<pointXArrayList.size();i++){
            String pointiString="POINT"+"("+pointXArrayList.get(i)+" "+pointYArrayList.get(i)+")";
         	Point pointi = (Point) reader.read(pointiString);
         	double distance=point.distance(pointi);  
         	GeoTreeMap.put(distance, geohash.encode(Double.valueOf(pointYArrayList.get(i)), Double.valueOf(pointXArrayList.get(i))));          
        }
			int i=0;
			Iterator<Double> iterator=GeoTreeMap.keySet().iterator();
			while(iterator.hasNext()){
				i++;
				if(i<=k){
					System.out.println(GeoTreeMap.get(iterator.next()));
				}
				else
					break;
			}
	}
	public static void main(String []args) throws Exception{
		long startTime = System.currentTimeMillis();//获取当前时间
		for(int i=0;i<10;i++){
			double X=FictitiousPolgon.getRandomNum(-180, 180);
			double Y=FictitiousPolgon.getRandomNum(-90, 90);
			new KNNTest().pointArray(X,Y,0.5,10);
		}
		long endTime = System.currentTimeMillis();
		System.out.println("程序运行时间："+(endTime-startTime)/10+"ms");	
		
		long startTime1 = System.currentTimeMillis();//获取当前时间
		for(int i=0;i<100;i++){
			double X=FictitiousPolgon.getRandomNum(-180, 180);
			double Y=FictitiousPolgon.getRandomNum(-90, 90);
			new KNNTest().sQuery(X,Y,0.5,10);
		}	
		long endTime1 = System.currentTimeMillis();
		System.out.println("程序运行时间："+(endTime1-startTime1)/100+"ms");	
	}
}
